package day08;

import java.util.Arrays;

/**
 * 3346. 执行操作后元素的最高频率 I
 * 给你一个整数数组 nums 和两个整数 k 和 numOperations 。
 *
 * 你必须对 nums 执行 操作  numOperations 次。每次操作中，你可以：
 *
 * 选择一个下标 i ，它在之前的操作中 没有 被选择过。
 * 将 nums[i] 增加范围 [-k, k] 中的一个整数。
 * 在执行完所有操作以后，请你返回 nums 中出现 频率最高 元素的出现次数。
 *
 * 一个元素 x 的 频率 指的是它在数组中出现的次数。
 */

public class No3346 {
    public int maxFrequency(int[] nums, int k, int numOperations) {
        int ans=1, l=0, r=0, i=0;
        int len = nums.length;
        Arrays.sort(nums);
        int min=nums[0], max=nums[len-1];
        for(int num=min; num<=max; num++){
            // 窗口左边界
            while(l < len-1 && nums[l]<num-k) l++;
            // 窗口右边界
            while(r+1<len && nums[r+1]<=num+k) r++;
            // 更新居中指针
            while(i < len-1 && nums[i]<num){
                i++;
            }
            // 统计重复
            int repeat = 0;
            if(nums[i] == num){
                while(i < len && nums[i]==num){
                    i++;
                    repeat++;
                }
            }
            // 计数，按条件取舍
            int frequency = Math.min(r-l+1, numOperations+repeat);
            // 取最值
            ans = Math.max(ans, frequency);
        }
        return ans;
    }
}
